package com.yileiqian.util;

public class Stack<T> {

	public static Stack<Integer> sort(Stack<Integer> s) {
		Stack<Integer> r = new Stack<Integer>();
		while (s.hasNext()) {
			int temp = s.pop();
			while (r.hasNext() && r.peek() < temp) {
				s.push(r.pop());
			}
			r.push(temp);
		}
		return r;
	}

	private Node<T> node;

	public Stack() {

	}

	public boolean hasNext() {
		return node != null;
	}

	public void push(T value) {
		if (node == null) {
			node = new Node<T>(value);
		} else {
			Node<T> newNode = new Node<T>(value);
			newNode.setNext(node);
			node = newNode;
		}
	}

	public T pop() {
		if (node == null) {
			throw new NullPointerException();
		}
		T value = node.getValue();
		node = node.next();
		return value;
	}

	public T peek() {
		return node.getValue();
	}

	public String toString() {
		StringBuffer buffer = new StringBuffer();

		Node<T> n = node;

		while (n != null) {
			buffer.append(n.getValue());
			buffer.append(' ');
			n = n.next();
		}

		return buffer.toString();
	}

	public static void main(String args[]) {
		Stack<Integer> s = new Stack<Integer>();
		s.push(10);
		s.push(6);
		s.push(8);
		s.push(9);
		s.push(7);
		System.out.println(s);
		System.out.println(Stack.sort(s));
	}
}
